package cn.wit.testalgorithms;

import java.util.Arrays;
import java.util.Stack;

/**
 * 496.下一个更大的元素
 * 暴搜法
 * 
 * @author 16604
 *
 */
public class DemoNextMaxNumber {
	public static void main(String[] args) {

		int[] nums1 = { 4, 1, 2 };
		int[] nums2 = { 1, 3, 4, 2 };

		System.out.println(Arrays.toString(nextGreaterElement(nums1, nums2)));

	}

	public static int[] nextGreaterElement(int[] nums1, int[] nums2) {

		// new一个新的栈出来,用来存放较大元素
		int[] a = new int[nums1.length];

		// 定义一个标识变量，用来记录有没有最大元素
		boolean flag;

		// 因为nums1为nums2的子集，所以，nums2总是会比nums1要长
		for (int i = 0; i < nums1.length; i++) {

			flag = false;

			// 从i的当前位置找寻右边里面遇到的第一个最大的一个元素
			for (int j = 0; j < nums2.length; j++) {
				// 满足条件就跳出当前循环

				if (nums1[i] == nums2[j]) {
					// 边界条件判断
					if (j == nums2.length - 1) {
						// a[i]=-1;
						break; // 跳出当前，进行下一个数比较
					} else {

						// 接下来才正式开始寻找
						for (int k = j; k < nums2.length; k++) {
							if (nums2[k] > nums1[i]) {
								flag = true;
								a[i] = nums2[k];
								break;
							}
						}
					}
				}
			}
			if (flag == false) {
				a[i] = -1;
			}
		}
		return a;
	}
}
